package com.example.demo.leetcode.classics150;

import java.util.*;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _96最小基因变化
 * @description
 * @date 2023/08/08 16:47
 * <p>
 * ******************************************************
 */
public class _96最小基因变化 {


    /**
     * 基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。
     * <p>
     * 假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
     * <p>
     * 例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。
     * 另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。
     * （变化后的基因必须位于基因库 bank 中）
     * <p>
     * 给你两个基因序列 start 和 end ，以及一个基因库 bank ，
     * 请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。
     * <p>
     * 注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * 输入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
     * 输出：1
     * 示例 2：
     * <p>
     * 输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
     * 输出：2
     * 示例 3：
     * <p>
     * 输入：start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
     * 输出：3
     * <p>
     * <p>
     * 提示：
     * <p>
     * start.length == 8
     * end.length == 8
     * 0 <= bank.length <= 10
     * bank[i].length == 8
     * start、end 和 bank[i] 仅由字符 ['A', 'C', 'G', 'T'] 组成
     *
     * @param startGene
     * @param endGene
     * @param bank
     * @return
     */
    public int minMutation1(String startGene, String endGene, String[] bank) {
        return 0;
    }


    public int minMutation(String start, String end, String[] bank) {
        // 定义三个集合，分别是合法基因集合，起始基因集合，目标基因集合
        Set<String> dict = new HashSet<>(), st = new HashSet<>(), ed = new HashSet<>();
        for (String s : bank) dict.add(s);
        // 基因库中不包含目标，则无法转换
        if (!dict.contains(end)) return -1;

        st.add(start);
        ed.add(end);
        // 宽搜
        return bfs(st, ed, dict, 0);
    }

    // 宽搜
    private int bfs(Set<String> st, Set<String> ed, Set<String> dict, int len) {
        // 起始集合为空，那么就无法到达目标
        if (st.size() == 0) return -1;
        // 优先从数量少的一端开始搜索，减少搜索量
        if (st.size() > ed.size()) return bfs(ed, st, dict, len);

        Set<String> next = new HashSet<>();
        char[] mode = {'A', 'C', 'G', 'T'};
        // 枚举起始集合可以一步转换的所有基因序列
        for (String s : st) {
            StringBuilder temp = new StringBuilder(s);
            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 4; j++) {
                    // 不包含相同的字符
                    if (s.charAt(i) == mode[j]) continue;
                    temp.setCharAt(i, mode[j]);
                    String cur = temp.toString();
                    // 终点集合中包含了当前字符，那么直接返回步数
                    if (ed.contains(cur)) return len + 1;
                    // 如果是合法序列，则加入下一个搜索集合中
                    if (dict.contains(cur)) {
                        next.add(cur);
                    }
                    temp.setCharAt(i, s.charAt(i));
                }
            }
        }
        // 搜索下一层
        return bfs(next, ed, dict, len + 1);
    }


}
